import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Created by asus on 2018/7/3.
 * 狄克斯特拉算法  让你能够找出加权图中前往X的最短路径
 */
public class DKSTLTest {
    public static void main(String[] args) {
        Map<String, Map<String, Integer>> graph = new HashMap<>();
        Map<String, Integer> mapStart = new HashMap<>();
        mapStart.put("a",6);
        mapStart.put("b",2);
        graph.put("start",mapStart);

        Map<String, Integer> graphA = new HashMap<>();
        graphA.put("fin",1);
        graph.put("a",graphA);

        Map<String, Integer> graphB = new HashMap<>();
        graphB.put("fin",5);
        graphB.put("a",3);
        graph.put("b",graphB);

        Map<String, Integer> graphFin = new HashMap<>();
        graph.put("fin",graphFin);

        Map<String, Integer> mapCost = new HashMap<>();
        mapCost.put("fin",Integer.MAX_VALUE);
        mapCost.put("a",6);
        mapCost.put("b",2);

        Map<String, String> mapParents = new HashMap<>();
        mapParents.put("fin",null);
        mapParents.put("a","start");
        mapParents.put("b","start");

        List<String> processed = new ArrayList<>();

        String node = findLowestCostNode(mapCost,processed);
        while (node != null){
            Integer cost = mapCost.get(node);
            Map<String, Integer>  neighbors = graph.get(node);
            for (String n : neighbors.keySet()){
                Integer newCost = cost + neighbors.get(n);
                if (mapCost.get(n) > newCost){
                    mapCost.put(n, newCost);
                    mapParents.put(n,node);
                }
            }
            processed.add(node);
            node = findLowestCostNode(mapCost,processed);
        }


        String a = "a";
        System.out.println("");

    }

    private static String findLowestCostNode(Map<String, Integer> mapCost, List<String> processed){
        Integer lowestCost = Integer.MAX_VALUE;
        String lowestCostNode = null;
        for (String node : mapCost.keySet()){
            Integer cost = mapCost.get(node);
            if (cost < lowestCost && !processed.contains(node)){
                lowestCost = cost;
                lowestCostNode = node;
            }
        }
        return lowestCostNode;
    }
}
